#include <vector>
#include <set>
#include <iostream>

using namespace std;

// 数组直接存入 set.  时间 O(nlogn)  空间 O(n)
class Intersect{
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
		// set  O(nlogn)
		set<int> record(nums1.begin(), nums1.end());

		// vector O(nlogn)
		set<int> resultSet;
		for(int i = 0; i < nums2.size(); ++i){
			// 集合中存在某元素, 则存入临时set
			if(record.find(nums2[i]) != record.end()){
				resultSet.insert(nums2[i]);
			}
				
		}
		// O(n)
		return vector<int>(resultSet.begin(), resultSet.end());
    }
};
